package stack;


import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/valid-parentheses/
 *
 * https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493261&idx=1&sn=2db0750fac363c7803b70a671a8a6b4e&chksm=9bd41885aca39193e8184749c7bf54f94d9bfbd30de2f5d7e982fcd5b7e9c794e9836f52e8f0&scene=178&cur_album_id=2165065740855443458#rd
 */
public class _20_有效的括号 {

    static Map<Character,Character> map = new HashMap<>();

    static {
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
    }

    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (map.containsKey(c)) {
                stack.push(c);
            } else if (map.containsValue(c)) {
                if (stack.isEmpty()) return false;
                Character pop = stack.pop();
                if (!map.get(pop).equals(c)) return false;
            } else {
                return false;
            }
        }

        return stack.isEmpty();
    }
}
